#include <bits/stdc++.h>
#include "caltime.cpp"
#include "read_data.cpp"
using namespace std;

// solving 
int best_ans;
string best_sol;
struct E{
    int cost,k,income,left;
    string sol;
    bool operator<(const E &a)const{
        return cost>a.cost;
    }
};

int get(int k,int cur_c){
	double res=0;
	for(int i=k;i<n;i++){
		if(cur_c>=bag[i].w)cur_c-=bag[i].w,res+=bag[i].v;
		else {
			res+=bag[i].v*cur_c/bag[i].w;
			break;
		}
	}
	return (int)res;
}

void bfs(){
    priority_queue<E> que;
    que.push({bag[0].v,1,0,c,"0"});
    if(c>=bag[0].w)que.push({0,1,bag[0].v,c-bag[0].w,"1"});
    while(que.size()){
        E now=que.top();que.pop();
        if(now.k>=n){
            if(now.income>best_ans)best_ans=now.income,best_sol=now.sol;
            continue;
        }
        if(get(now.k,now.left)+now.income<=best_ans)continue;
        que.push({now.cost+bag[now.k].w , now.k+1 , now.income , now.left , now.sol+"0" });
        if(now.left>=bag[now.k].w)que.push({now.cost , now.k+1 ,\
        now.income + bag[now.k].v , now.left - bag[now.k].w , now.sol+"1" });
    }
    return ;
}

void solve(int k){
    printf("data#%d :\n",k);
	printf("n: %d  c: %d \n",n,c);
	double T=0;
	for(int i=0;i<10;i++){
        best_ans=0;
        best_sol="";
		Start();
        bfs();
		End();
        T+=Cal_it();
	}
	printf("answer : %d \n",best_ans);
    cout << best_sol << "\n";
	printf("Ave-Time: %.4lfms\n",T/10);puts("");
}

int main(){
	read_file_names();
	freopen("branch_and_bound","w",stdout);
	for(int i=0;i<N;i++){
		read_data(i);
		solve(i); 
	}
}

